<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-13 14:18:36
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-13 15:17:52
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>对称二叉树</title>
</head>

<body>
    <script>

        // 比较的是根节点的左节点和右节点是否对称，比较的是两棵子树，
        // 思路，正是因为要遍历两棵树而且要比较内侧和外侧节点，所以准确的来说是一个树的遍历顺序是左右中，一个树的遍历顺序是右左中。
        // 一个是左中右，一个是右左中
        var isSymmetric = function (root) {
            //递归三部曲，遍历左右子树，
            // 确定递归的参数，和返回值
            const compareNode = function (left, right) {
                // 确定该终止情况
                if (left === null && right !== null || left != null && right === null) {
                    return false;
                } else if (left == null && right == null) {
                    return true;
                } else if (left.val !== right.val) {
                    return false;
                }

                // 确定单层递归
                let outside = compareNode(left.left, right.right);
                let inside = compareNode(left.right, right.left);
                return outside && inside;

            }

            if (root === null) {
                return true;
            }

            return compareNode(root.left, root.right);
        }

        // 队列实现迭代判断是否为对称二叉树
        var isSymmetric = function (root) {
            // 首先判断根节点是否为空
            if (root === null) {
                return true;
            }
            let queue = [];
            queue.push(root.left);
            queue.push(root.right);
            while (queue.length) {
                let leftNode = queue.shift();//左节点
                let rightNode = queue.shift();//右节点
                if (leftNode === null && rightNode === null) {
                    continue;
                }
                if (leftNode === null || rightNode === null || leftNode.val != rightNode.val) {
                    return false;
                }
                queue.push(leftNode.left);//左节点左孩子入队
                queue.push(rightNode.right);//右节点右孩子入队
                queue.push(leftNode.right);//左孩子右节点入队
                queue.push(rightNode.left);//右孩子左节点入队

            }

            return true;
        }


        //栈实现迭代判断是否是对称二叉树
        var isSymmetric = function (root) {
            //迭代方式判断是否是对称二叉树
            // 首先判断根节点是否是空
            if (root === null) {
                return true;
            }
            let stack = [];
            stack.push(root.left);
            stack.push(root.right);
            while (stack.length) {
                let rightNode = stack.pop();//左节点
                let leftRight = stack.pop();//右节点
                if (leftNode === null && rightNode === null) {
                    continue;
                }
                if (leftNode === null || rightNode === null || leftNode.val != rightNode.val) {
                    return false;
                }
                stack.push(leftNode.left);//左节点左孩子入队
                stack.push(rightNode.right);//右节点右孩子入队
                stack.push(leftNode.right);//左节点右孩子入队
                stack.push(rightNode.left);//右节点右孩子入队

            }

            return true;
        }






    </script>
</body>

</html>